package net.tp.algo.text.sa;

/**
 *
 * <p>Naive algorithm for LCP.</p>
 *
 *
 *
 * @author Trung Phan
 *
 */
public class NaiveLCP {

    public static int[] buildLCP(String text, int[] sa) {

        int n = text.length();
        assert sa.length == n;

        int[] lcp = new int[n];

        for (int i = 1; i < sa.length; i++) {
            lcp[i] = lcp(text, sa[i-1], sa[i]);
        }

        return lcp;
    }

    private static int lcp(String text, int from1, int from2) {
        int n = text.length();
        int h = 0;
        while (from1 < n && from2 < n && text.charAt(from1) == text.charAt(from2)) {
            from1++; from2++; h++;
        }
        return h;
    }

}
